package com.hyb.algorithm.data.struct.dp;

import com.alibaba.fastjson.JSON;
import com.alibaba.fastjson.JSONObject;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: huyanbing
 * @Date: 2021/9/6 2:25 下午
 * <p>
 * 46. 全排列
 * https://leetcode-cn.com/problems/permutations/
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums = [1,2,3]
 * 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
 */
public class Permute {

    public static void main(String[] args) {

        int[] nums = new int[]{1, 2, 3};

        Permute exe = new Permute();
        exe.permute(nums);
    }

    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        backtrack(list, new ArrayList<>(), nums);
        return list;
    }


    private void backtrack(List<List<Integer>> list, List<Integer> tempList, int[] nums) {
        if (tempList.size() == nums.length) {
            list.add(new ArrayList<>(tempList));
        } else {
            for (int i = 0; i < nums.length; i++) {
                //已经存在的元素 跳过
                if (tempList.contains(nums[i])) {
                    continue;
                }
                tempList.add(nums[i]);
                //向后继续添加
                backtrack(list, tempList, nums);
                //将 tempList 刚添加的元素 去掉， 尝试新的元素
                tempList.remove(tempList.size() - 1);

                //System.out.println(JSONObject.toJSON(tempList));
            }
        }

    }


}

